LoginSignup
mmhsivgnhmf
@mmhsivgnhmf (aaa)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

java 教えてください

Q&AClosed

javaの問題をしていますが全然わかりません

1~7の2枚ずつのカード14枚を使って以下の条件になるように、隙間なく並べられるすべてのパターンを調べるプログラムを作成してください。 なお、左右反転しただけのパターンは除外する。

条件
1と1のカードの間には1枚のカードが入る。
2と2のカードの間には2枚のカードが入る。
3と3のカードの間には2枚のカードが入る。
4と4のカードの間には2枚のカードが入る。
5と5のカードの間には2枚のカードが入る。
6と6のカードの間には2枚のカードが入る。
7と7のカードの間には7枚のカードが入る。

実行結果

①⑦①②⑤⑥②③④⑦⑤③⑥④
①⑦①②⑥④②⑤③⑦④⑥③⑤
①⑥①⑦②④⑤②⑥③④⑦⑤③
①⑤①⑥⑦②④⑤②③⑥④⑦③
①④①⑤⑥⑦④②③⑤②⑥③⑦
①④①⑥⑦③④⑤②③⑥②⑦⑤
①⑥①③⑤⑦④③⑥②⑤④②⑦
①⑤①⑦③④⑥⑤③②④⑦②⑥
①⑤①⑥③⑦④⑤③②⑥④②⑦
①⑤①④⑥⑦③⑤④②③⑥②⑦
⑤①⑦①⑥②⑤④②③⑦⑥④③
④①⑦①⑥④②⑤③②⑦⑥③⑤
④①⑥①⑦④③⑤②⑥③②⑦⑤
⑦①③①⑥④③⑤⑦②④⑥②⑤
⑦①④①⑥③⑤④⑦③②⑥⑤②
⑥①⑤①⑦③④⑥⑤③②④⑦②
④⑥①⑦①④⑤②⑥③②⑦⑤③
⑦③①⑥①③④⑤⑦②⑥④②⑤
④⑥①⑦①④③⑤⑥②③⑦②⑤
⑤⑥①⑦①③⑤④⑥③②⑦④②
⑦④①⑤①⑥④③⑦⑤②③⑥②
⑤⑦①④①⑥⑤③④⑦②③⑥②
③⑥⑦①③①④⑤⑥②⑦④②⑤
⑤⑦④①⑥①⑤④③⑦②⑥③②
②⑥⑦②①⑤①④⑥③⑦⑤④③
④⑤⑥⑦①④①⑤③⑥②⑦③②
全部で26通りでした。

0

3Answer

テンプレートには自分で試したことという項目があります.すなわち回答者がまるまる答えを教えてくれるわけではないので,丸投げのような形で質問するのはやめましょう.

あと明らかに出力例と問題文の条件に齟齬があるので,質問の投稿前にプレビューして確認してください.

2

これはJAVAの問題ではなく、アルゴリズムの問題ですね。
アルゴリズムを考える力はプログラマーの大事な基礎力です。
どうか諦めずに挑戦してみてください。

0

Javaというより、アルゴリズムの問題ですね。

解き方はいくつもあると思いますが、深さ優先探索で解いてみました。
言語はSwiftです。Javaコードは後ほどアップします。

import Foundation

let main: () = {
    let K = [
        [1, 0, 1],
        [2, 0, 0, 2],
        [3, 0, 0, 0, 3],
        [4, 0, 0, 0, 0, 4],
        [5, 0, 0, 0, 0, 0, 5],
        [6, 0, 0, 0, 0, 0, 0, 6],
        [7, 0, 0, 0, 0, 0, 0, 0, 7],
    ]
    func isPlaceable(_ n: Int, _ p: Int, _ g: inout [Int]) -> Bool {
        let k = K[n]
        if p + k.count > g.count { return false }
        for m in 0 ..< k.count {
            if k[m] != 0 {
                if g[p + m] != 0 { return false }
                g[p + m] = k[m]
            }
        }
        return true
    }
    var ans = Set<[Int]>()
    func dfs(_ n: Int, _ g: [Int]) {
        if n == 7 {
            if !ans.contains(g.reversed()) {
                ans.insert(g)
            }
            return
        }
        for p in 0 ..< g.count {
            var g = g
            if !isPlaceable(n, p, &g) { continue }
            dfs(n + 1, g)
        }
    }
    dfs(0, [Int](repeating: 0, count: 14))
    ans.sorted{ $0.lexicographicallyPrecedes($1) }.forEach {
        $0.forEach { print($0, terminator: " ") }
        print()
    }
}()

0

Comments

  1. 上のSwiftコードをChatGPTにJavaに変換してもらったコードです。

    import java.util.HashSet;
    import java.util.Set;
    
    public class Main {
        static int[][] K = {
                {1, 0, 1},
                {2, 0, 0, 2},
                {3, 0, 0, 0, 3},
                {4, 0, 0, 0, 0, 4},
                {5, 0, 0, 0, 0, 0, 5},
                {6, 0, 0, 0, 0, 0, 0, 6},
                {7, 0, 0, 0, 0, 0, 0, 0, 7}
        };
    
        static boolean isPlaceable(int n, int p, int[] g) {
            int[] k = K[n];
            if (p + k.length > g.length) return false;
            for (int m = 0; m < k.length; m++) {
                if (k[m] != 0) {
                    if (g[p + m] != 0) return false;
                    g[p + m] = k[m];
                }
            }
            return true;
        }
    
        static Set<int[]> ans = new HashSet<>();
    
        static void dfs(int n, int[] g) {
            if (n == 7) {
                if (!ans.contains(reverse(g))) {
                    ans.add(g);
                }
                return;
            }
            for (int p = 0; p < g.length; p++) {
                int[] clonedG = g.clone();
                if (!isPlaceable(n, p, clonedG)) continue;
                dfs(n + 1, clonedG);
            }
        }
    
        static int[] reverse(int[] array) {
            int[] reversedArray = new int[array.length];
            for (int i = 0; i < array.length; i++) {
                reversedArray[i] = array[array.length - 1 - i];
            }
            return reversedArray;
        }
    
        public static void main(String[] args) {
            dfs(0, new int[14]);
            ans.stream().sorted((a, b) -> {
                for (int i = 0; i < a.length; i++) {
                    if (a[i] != b[i]) return a[i] - b[i];
                }
                return 0;
            }).forEach(g -> {
                for (int i : g) {
                    System.out.print(i + " ");
                }
                System.out.println();
            });
        }
    }
    

    実行してみると、左右反転の除外が効いていないです。なぜ?

  2. 自己レスです。

    実行してみると、左右反転の除外が効いていないです。なぜ?

    if (!ans.contains(reverse(g))) {
    ↑この場合、containsメソッドを使うなら、hashCodeメソッドとequalsメソッドを実装する必要があるようです。
    そこで、int[]やめてStringで実装しました。

    import java.util.HashSet;
    import java.util.Set;
    import java.util.Arrays;
    import java.util.Collections;
    
    public class Main {
        static String[] K = {
                "101",
                "2002",
                "30003",
                "400004",
                "5000005",
                "60000006",
                "700000007"
        };
    
        static boolean isPlaceable(int n, int p, String g) {
            String k = K[n];
            if (p + k.length() > g.length()) return false;
            for (int m = 0; m < k.length(); m++) {
                if (k.charAt(m) != '0') {
                    if (g.charAt(p + m) != '0') return false;
                }
            }
            return true;
        }
    
        static String place(int n, int p, String g) {
            String k = K[n];
            if (p + k.length() > g.length()) return g;
            for (int m = 0; m < k.length(); m++) {
                if (k.charAt(m) != '0') {
                    if (g.charAt(p + m) != '0') return g;
                }
            }
            String s = "";
            for (int m = 0; m < g.length(); m++) {
                if (p <= m && m < p + k.length()) {
                    if (k.charAt(m - p) != '0') {
                        s += k.charAt(m - p);
                    } else {
                        s += g.charAt(m);
                    }
                } else {
                    s += g.charAt(m);
                }
            }
            return s;
        }
    
        static String reverse(String aString) {
            if (aString == null) return aString;
    		String reverseString = "";
    		for (int i = aString.length() - 1; i >= 0; i--) {
    			reverseString = reverseString + aString.charAt(i);
    		}
    		return reverseString;
        }
    
        static Set<String> ans = new HashSet<>();
    
        static void dfs(int n, String g) {
            if (n == 7) {
                if (!ans.contains(reverse(g))) {
                    ans.add(g);
                }
                return;
            }
            for (int p = 0; p < g.length(); p++) {
                if (!isPlaceable(n, p, g)) continue;
                String nextG = place(n, p, g);
                dfs(n + 1, nextG);
            }
        }
    
        public static void main(String[] args) {
            dfs(0, "00000000000000");
            String array[] = ans.toArray(String[]::new);
            Arrays.sort(array);
            for (String s : array) {
                System.out.println(s);
            };
        }
    }
    

Your answer might help someone💌